import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;

public class Solution327 {
    public static class BIT{

        int[] f;
        int n;

        public BIT(int k){
            f=new int[k+1];
            n=k;
        }

        private int lowBit(int x){
            return x&(-x);
        }

        public int query(int k){
            int t=0;
            while (k>0){
               t=t+f[k];
               k-=lowBit(k);
            }
            return t;
        }

        public void update(int k,int d){
            while (k<=n){
                f[k]+=d;
                k+=lowBit(k);
            }
        }
    }

    public int countRangeSum(int[] nums, int lower, int upper) {
        Set<Long> set=new TreeSet<>();
        long[] sum=new long[nums.length+1];
        for (int i=0;i<nums.length;i++){
            sum[i+1]=sum[i]+nums[i];
        }
        for (long i : sum) {
            set.add(i);
            set.add(i-upper);
            set.add(i-lower);
        }
        int id=0;
        Map<Long,Integer> map=new HashMap<>();
        for (Long aLong : set) {
            id++;
            map.put(aLong,id);
        }
        BIT bit=new BIT(id);
        int ans=0;
        bit.update(map.get(0L),1);
        for (int i=1;i<=nums.length;i++){
            int l=map.get(sum[i]-upper)-1;
            int r=map.get(sum[i]-lower);
            ans=ans+bit.query(r)-bit.query(l);
            bit.update(map.get(sum[i]),1);
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution327().countRangeSum(new int[]{-2,5,-1},-2,2));
    }
}
